package datastructure.tree.bst2;


/**
 * 二叉搜索树-put操作
 *
 * @author 杨 强
 * @package datastructure.tree.bst2
 * @createTime 2023-03-21 21:50
 */
public class BST03Put {
    public static void main(String[] args) {
        /*
                        3
                       / \
                      2   4
                     /
                    1
         */
        TreeNode node1 = new TreeNode(1, "1", null, null);
        TreeNode node2 = new TreeNode(2, "2", node1, null);
        TreeNode node4 = new TreeNode(4, "3", null, null);
        TreeNode node3 = new TreeNode(3, "4", node2, node4);
        BST03Put bst01 = new BST03Put(node3);
        bst01.put(1, 4);
        System.out.println(bst01);
    }

    /**
     * 二叉搜索树的根节点
     */
    TreeNode root;

    /**
     * 构造函数,设置二叉树根节点
     * @param root 根节点
     */
    public BST03Put(TreeNode root) {
        this.root = root;
    }

    /**
     * put方法
     * @param key 元素key
     * @param value 元素值
     */
    public void put(int key, Object value){

        TreeNode node = root;
        // 没有找到的话这个节点就是put的key节点的父节点(仔细想想)
        TreeNode parent = null;
        while (node != null){
            parent = node;
            if (node.key > key){
                node = node.left;// 往左找
            }else if (node.key < key){
                node = node.right; // 往右找
            }else {
                // key存在:更新
                node.value = value;
                return;
            }
        }

        // key不存在: 添加到合适的位置
        if (parent == null){
            root = new TreeNode(key, value);
            return;
        }
        if (key > parent.key){
            // 放右边
            parent.right = new TreeNode(key, value);
        }else {
            // 放左边
            parent.left = new TreeNode(key, value);
        }

    }
}
